/*
 * @(#) BTIndexPage.java   98/05/14
 * Copyright (c) 1998 UW.  All Rights Reserved.
 *         Author: Xiaohu Li (xioahu@cs.wisc.edu)
 *
 */


package btree;
import global.PageId;
import global.RID;

import java.io.IOException;

import org.omg.CORBA.DataOutputStream;

import exceptions.*;
import diskmgr.Page;

/**
 * A BTIndexPage is an index page on a B+ tree.  It holds abstract 
 * {key, PageId} pairs; it doesn't know anything about the keys 
 * (their lengths or their types), instead relying on the abstract
 * interface in BT.java
 * See those files for our {key,data} pairing interface and implementation.
 */
public class BTIndexPage extends BTSortedPage{
 

  /** pin the page with pageno, and get the corresponding BTIndexPage,
   * also it sets the type of node to be NodeType.INDEX.
   *@param pageno Input parameter. To specify which page number the
   *  BTIndexPage will correspond to.
   *@param keyType either AttrType.attrInteger or AttrType.attrString.
   *   Input parameter.
   *@exception IOException error from the lower layer
   *@exception ConstructPageException error when BTIndexpage constructor
   */
  public BTIndexPage(PageId pageno, int keyType) 
    throws IOException, 
	   ConstructPageException
    {
      super(pageno, keyType);
      setType(NodeType.INDEX);
    }
  
  /**associate the BTIndexPage instance with the Page instance,
   * also it sets the type of node to be NodeType.INDEX.
   *@param page input parameter. To specify which page  the
   *  BTIndexPage will correspond to. 
   *@param keyType either AttrType.attrInteger or AttrType.attrString.
   *  Input parameter.    
   *@exception IOException  error from the lower layer
   *@exception ConstructPageException error when BTIndexpage constructor
   */
  public BTIndexPage(Page page, int keyType) 
    throws IOException, 
	   ConstructPageException
    {
      super(page, keyType);
      setType(NodeType.INDEX);
    }  
  
  /* new a page, associate the BTIndexPage instance with the Page instance,
   * also it sets the type of node to be NodeType.INDEX.
   *@param keyType either AttrType.attrInteger or AttrType.attrString.
   *  Input parameter.    
   *@exception IOException  error from the lower layer
   *@exception ConstructPageException error when BTIndexpage constructor
   */
  public BTIndexPage( int keyType) 
    throws IOException, 
	   ConstructPageException
    {
      super(keyType);
      setType(NodeType.INDEX);
    }    
  public KeyDataEntry split(KeyDataEntry dataEntry, 
          PageId currentPID,BTreeHeaderPage headerPage) throws ConstructPageException, IOException,
          IteratorException, IndexInsertRecException, DeleteRecException,
          KeyNotMatchException, NodeNotMatchException, ConvertException,
          UnpinPageException {
   int keyType = headerPage.getKeyType();
   
  // PageId currentPID = this.getCurPage();
  KeyDataEntry tmpEntry;
  RID delRid = new RID();
  // BTIndexPage currentIndexPage = this;
  BTIndexPage newIndexPage = new BTIndexPage(keyType);
  PageId newIndexPageId = newIndexPage.getCurPage();
//  DataOutputStream trace = BTreeFile.trace;
//  if (trace != null) {
//          if (headerPage.getRoot().pid != currentPID.pid)
//                  trace.writeBytes("SPLIT node " + currentPID
//                                  + " IN nodes " + currentPID + " "
//                                  + newIndexPageId + BTreeFile.lineSep);
//          else
//                  trace.writeBytes("ROOTSPLIT IN nodes " + currentPID
//                                  + " " + newIndexPageId + BTreeFile.lineSep);
//          trace.flush();
//  }
  for (tmpEntry = this.getFirst(delRid); tmpEntry != null; tmpEntry = this
                  .getFirst(delRid)) {
          newIndexPage.insertKey(tmpEntry.key,
                          ((IndexData) tmpEntry.data).getData());
          this.deleteSortedRecord(delRid);
  }
  RID firstRid = new RID();
  KeyDataEntry undoEntry = null;
  for (tmpEntry = newIndexPage.getFirst(firstRid); (this
                  .available_space() > newIndexPage.available_space()); tmpEntry = newIndexPage
                  .getFirst(firstRid)) {
          // now insert the <key,pageId> pair on the new
          // index page
          undoEntry = tmpEntry;
          this.insertKey(tmpEntry.key, ((IndexData) tmpEntry.data).getData());
          newIndexPage.deleteSortedRecord(firstRid);
  }
  if (this.available_space() < newIndexPage.available_space()) {

          newIndexPage.insertKey(undoEntry.key,
                          ((IndexData) undoEntry.data).getData());

          this.deleteSortedRecord(new RID(this.getCurPage(), (int) this
                          .getSlotCnt() - 1));
  }
  // check whether <newKey, newIndexPageId>
  // will be inserted
  // on the newly allocated or on the old index page

  tmpEntry = newIndexPage.getFirst(firstRid);

  if (BT.keyCompare(dataEntry.key, tmpEntry.key) >= 0) {
          // the new data entry belongs on the new index page
          newIndexPage.insertKey(dataEntry.key,
                          ((IndexData) dataEntry.data).getData());
  } else {
          this.insertKey(dataEntry.key,
                          ((IndexData) dataEntry.data).getData());

          int i = (int) this.getSlotCnt() - 1;
          tmpEntry = BT.getEntryFromBytes(this.getpage(),
                          this.getSlotOffset(i), this.getSlotLength(i), keyType,
                          NodeType.INDEX);

          newIndexPage.insertKey(tmpEntry.key,
                          ((IndexData) tmpEntry.data).getData());

          this.deleteSortedRecord(new RID(this.getCurPage(), i));

  }
  BTreeFile.unpinPage(currentPID);
  dataEntry = newIndexPage.getFirst(delRid);
  newIndexPage.setPrevPage(((IndexData) dataEntry.data).getData());

  // delete first record on new index page since it is given up
  newIndexPage.deleteSortedRecord(delRid);
  BTreeFile.unpinPage(newIndexPageId);
//if (trace != null) {
//        trace_children(currentIndexPageId);
//        trace_children(newIndexPageId);
//}
  ((IndexData) dataEntry.data).setData(newIndexPageId);
  return dataEntry;
}
  
  
  /** It inserts a <key, pageNo> value into the index page,
   *@key  the key value in <key, pageNO>. Input parameter. 
   *@pageNo the pageNo  in <key, pageNO>. Input parameter.
   *@return It returns the rid where the record is inserted;
   null if no space left.
   *@exception IndexInsertRecException error when insert
   */
   public RID insertKey(KeyClass key, PageId pageNo) 
      throws  IndexInsertRecException
    {
      RID rid;
      KeyDataEntry entry;
      try {
        entry = new KeyDataEntry( key, pageNo); 
        rid=super.insertRecord( entry );
        return rid;
      }
      catch ( Exception e) {       
        throw new IndexInsertRecException(e, "Insert failed");
        
      }
    }
  
  /*  OPTIONAL: fullDeletekey 
   * This is optional, and is only needed if you want to do full deletion.
   * Return its RID.  delete key may != key.  But delete key <= key,
   * and the delete key is the first biggest key such that delete key <= key 
   *@param key the key used to search. Input parameter.
   *@exception IndexFullDeleteException if no record deleted or failed by
   * any reason
   *@return  RID of the record deleted. Can not return null.
   */
//  RID deleteKey(KeyClass key) 
//    throws IndexFullDeleteException 
//    {
//      KeyDataEntry  entry;
//      RID rid=new RID(); 
//      
//      
//      try {
//	
//	entry = getFirst(rid);
//	
//	if (entry == null) 
//	  //it is supposed there is at least a record
//	  throw new IndexFullDeleteException(null, "No records found");
//	
//	
//	if ( BT.keyCompare(key, entry.key)<0 )  
//	  //it is supposed to not smaller than first key
//	  throw new IndexFullDeleteException(null, "First key is bigger");
//	
//	
//	while (BT.keyCompare(key, entry.key) > 0) {
//	  entry = getNext(rid );
//	  if (entry == null)
//            break;
//	}
//	
//	if (entry == null) rid.slotNo--;
//	else if (BT.keyCompare(key, entry.key) != 0)
//	  rid.slotNo--; // we want to delete the previous key
//	
//	deleteSortedRecord(rid);
//	return rid;
//      }
//      catch (Exception e) {
//        throw new IndexFullDeleteException(e, "Full delelte failed"); 
//      }
//    } // end of deleteKey
//  
//  
  
  /* 
   * This function encapsulates the search routine to search a
   * BTIndexPage by B++ search algorithm 
   *@param key  the key value used in search algorithm. Input parameter. 
   *@return It returns the page_no of the child to be searched next.
   *@exception IndexSearchException Index search failed;
   */
  PageId getPageNoByKey(KeyClass key) 
    throws IndexSearchException         
    {
      KeyDataEntry entry;
      int i;
      
      try {
	
	for (i=getSlotCnt()-1; i >= 0; i--) {
	  entry= BT.getEntryFromBytes( getpage(),getSlotOffset(i), 
				       getSlotLength(i), keyType, NodeType.INDEX);
	  
	  if (BT.keyCompare(key, entry.key) >= 0)
	    {
	      return ((IndexData)entry.data).getData();
	    }
	}
	
	return getPrevPage();
      } 
      catch (Exception e) {
	throw new IndexSearchException(e, "Get entry failed");
      }   
      
    } // getPageNoByKey
  
  
  
  /**  Iterators. 
   * One of the two functions: getFirst and getNext
   * which  provide an iterator interface to the records on a BTIndexPage.
   *@param rid It will be modified and the first rid in the index page
   * will be passed out by itself. Input and Output parameter. 
   *@return return the first KeyDataEntry in the index page.
   *null if NO MORE RECORD
   *@exception IteratorException  iterator error
   */
//  public KeyDataEntry getFirst(RID rid) 
//    throws IteratorException
//    {
//      
//      KeyDataEntry  entry; 
//      
//      try { 
//	rid.pageNo = getCurPage();
//	rid.slotNo = 0; // begin with first slot
//	
//	if ( getSlotCnt() == 0) {
//	  return null;
//	}
//	
//	entry=BT.getEntryFromBytes( getpage(),getSlotOffset(0), 
//				    getSlotLength(0),
//				    keyType, NodeType.INDEX);
//	
//	return entry;
//      } 
//      catch (Exception e) {
//	throw new IteratorException(e, "Get first entry failed");
//      }
//      
//    } // end of getFirst
  
  public KeyDataEntry getFirst(RID rid) throws IteratorException {
      KeyDataEntry entry;

      try {
              rid.pageNo = getCurPage();
              rid.slotNo = 0; // begin with first slot

              if (getSlotCnt() <= 0) {
                      return null;
              }

              entry = BT.getEntryFromBytes(getpage(), getSlotOffset(0),
                              getSlotLength(0), keyType, NodeType.INDEX);

              return entry;
      } catch (Exception e) {
              throw new IteratorException(e, "Get first entry failed");
      }

}
  /**Iterators.  
   * One of the two functions: get_first and get_next which  provide an
   * iterator interface to the records on a BTIndexPage.
   *@param rid It will be modified and next rid will be passed out by itself.
   *         Input and Output parameter.
   *@return return the next KeyDataEntry in the index page. 
   *null if no more record
   *@exception IteratorException iterator error
   */
  public KeyDataEntry getNext (RID rid)
    throws  IteratorException 
    {
      KeyDataEntry  entry; 
      int i;
      try{
	rid.slotNo++; //must before any return;
	i=rid.slotNo;
	
	if ( rid.slotNo >= getSlotCnt())
	  {
	    return null;
	  }
	
	entry=BT.getEntryFromBytes(getpage(),getSlotOffset(i), 
				   getSlotLength(i),
				   keyType, NodeType.INDEX);
	
	return entry;
      } 
      catch (Exception e) {
	throw new IteratorException(e, "Get next entry failed");
      }
    } // end of getNext
  
  
  /** Left Link 
   *  You will recall that the index pages have a left-most
   *  pointer that is followed whenever the search key value
   *  is less than the least key value in the index node. The
   *  previous page pointer is used to implement the left link.
   *@return It returns the left most link. 
   *@exception IOException error from the lower layer
   */
  protected PageId getLeftLink() 
    throws IOException
    {
      return getPrevPage(); 
    }
  
  /** You will recall that the index pages have a left-most
   *  pointer that is followed whenever the search key value
   *  is less than the least key value in the index node. The
   *  previous page pointer is used to implement the left link.
   * The function sets the left link.
   *@param left the PageId of the left link you wish to set. Input parameter.
   *@exception IOException I/O errors
   */ 
  protected void setLeftLink(PageId left) 
    throws IOException
    { 
      setPrevPage(left); 
    }
  
  
  
};
